package com.zzy.study.arithmetic;

import java.util.Arrays;  

/** 
 * 堆排序. 
 * 
 */  
public class HeapSort {  
  
    private static int parentIdx(int childIdx) {  
        return (childIdx - 1) / 2;  //索引从0开始, 注意childIdx=0时返回0  
    }  
  
    private static int leftChildIdx(int parentIdx) {  
        return parentIdx*2 + 1;  
    }  
  
    /** 
     * 构建大顶堆. 
     */  
    private static void buildMaxHeap(int[] datas) {  
        int lastIdx = datas.length -1;  
        for(int i=parentIdx(lastIdx); i>=0; i--) {   //几个父节点
            int k = i;           //当前父节点k=i
            while(leftChildIdx(k) <= lastIdx) {  
                int j = leftChildIdx(k);  
                if(j < lastIdx) {    //有两个孩子  
                    if(datas[j] <= datas[j+1]) { //右孩子比较大, 选择大的  
                        j++;  
                    }  
                }  
  
                if(datas[k] >= datas[j]) {    //父的比较大  
                    break;  
                } else {  
                    SortUtil.swap(datas, k, j);  
                    k = j;            //父节点重新赋值为原父节点的左孩子节点或者右孩子节点
                }  
            }  
        }  
    }  
  
    /** 
     * 堆顶改变, 要维护大顶堆. 
     */  
    private static void maintainMaxHeap(int[] datas, int lastIdx) {  
        int k = 0;  
        while(k <= parentIdx(lastIdx)) {  
            int j = leftChildIdx(k);  
            if(j < lastIdx) {    //有两个孩子  
                if(datas[j] <= datas[j+1]) { //j+1 比较大, 选择大的  
                    j++;  
                }  
            }  
            if(datas[k] < datas[j]) {    //父结点比较小  
                SortUtil.swap(datas, k, j);  
                k = j;  
            } else {  
                break;  
            }
        }  
    }  
  
    public static int[] sort(int[] datas) {  
        buildMaxHeap(datas);  
        int lastIdx = datas.length - 1;  
        while(lastIdx > 0) {  
            SortUtil.swap(datas, 0, lastIdx);   
            lastIdx--;  
            if(lastIdx > 0) {  
                maintainMaxHeap(datas, lastIdx);  
            }  
        }  
        return datas;  
    }  
  
    public static void main(String[] args) {  
        int[] datas = {5,1,3,4,9,2,7,6,5};//{2, 9, 3, 7, 8, 6, 4, 5, 0, 1};  
  
        sort(datas);  
        System.out.println(Arrays.toString(datas));  
  
    }  
  
}  